package com.leetcode;

import ds.TreeNode;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No124
 * @description 124. 二叉树中的最大路径和
 * @date 2021/3/9 下午7:41
 */
public class No124 {

    private static int maxValue = Integer.MIN_VALUE;

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(-10);
        TreeNode t2 = new TreeNode(9);
        TreeNode t3 = new TreeNode(20);
        TreeNode t4 = new TreeNode(15);
        TreeNode t5 = new TreeNode(7);
        t1.left = t2;
        t1.right = t3;
        t3.left = t4;
        t3.right = t5;
        int maxPath = maxPathSum(t1);
        System.out.println(maxPath);

    }
    public static int maxPathSum(TreeNode root) {
        if(root == null){
            return 0;
        }
        helper(root);
        return maxValue;
    }

    private static int helper(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftMax = Math.max(0,helper(root.left));
        int rightMax = Math.max(0,helper(root.right));
        maxValue = Math.max(maxValue,leftMax + rightMax + root.val);
        return Math.max(leftMax,rightMax) + root.val;
    }

}
